1. Field of the Invention
The present invention relates to error diffusion processing for an image.
2. Description of the Related Art
An image output apparatus which can express only two tones by ON/OFF of a dot per pixel, like an inkjet printer, expresses a multi-tone image by performing halftone processing for multi-tone image data. The halftone processing is image processing for pseudo-expressing multiple tones using a small number of tones such as two tones. Halftone processing is achieved by various methods. Among them, an error diffusion method is most popular because of excellent tonality and high resolution of a processed image. The error diffusion method is image processing of sequentially diffusing the difference (quantization error) between a pixel value before quantization and one after quantization in the pixel of interest to unprocessed pixels around the pixel of interest at predetermined ratios.
When processing image data, it needs to be developed in the memory. In terms of the cost, it is difficult to equip a device with a memory having a storage capacity capable of developing all image data of one image, especially for low-end devices such as a home printer. Under the circumstances, an image is divided into a plurality of partial regions, and the partial regions are developed one by one in the memory and undergo image processing.
Another factor that raises the cost of a device is increasing storage capacity of a memory for delay along with a recent increase in resolution of image data to be processed. As a solution to this problem, for example, in an invention disclosed in Japanese Patent No. 3733826 (patent literature 1), an image is divided into a plurality of bands, and image processing is performed by scanning them in a direction perpendicular to the band division direction. This implements an image processing apparatus in which the storage capacity of the memory for delay depends not on the resolution of image data to be processed but on the band height.
However, the image quality sometimes degrades when an image is divided into a plurality of regions and halftone processing is performed using the error diffusion method. More specifically, no error is diffused from a given region to the next one, and the continuity of error diffusion processing is lost at the boundary between the regions. This results in a dot pattern mismatch at the boundary between the regions. The dot pattern mismatch at the boundary between the regions is observed as a thread, which is visually conspicuous image quality degradation.
A method for solving this problem is, for example, a technique disclosed in an invention in Japanese Patent Laid-Open No. 63-310269 (patent literature 2). According to this technique, an error (diffusion error) diffused when a pixel near the boundary of a region was processed is stored in a memory. The diffusion error stored in the memory is used when processing a pixel near the boundary of a region to be processed next. This invention discloses a method of setting an overlapping region for error diffusion processing near the boundary and approximating an error to be diffused to a pixel near the boundary of the region. However, even the invention in patent literature 2 cannot accurately approximate an error to be diffused to a pixel near the boundary.
An example in which an image is divided into bands and error diffusion processing is performed will be explained with reference to FIG. 1. An image 100 is divided into bands 101, 102, and 103. Error diffusion processing is done by alternately scanning pixels in a direction (top-to-bottom direction in FIG. 1) that is perpendicular to the longitudinal direction of the band. This scanning can prevent one-sided diffusion of an error, improving the image quality.
FIGS. 2A and 2B exemplify error diffusion matrices. FIG. 2A shows an error diffusion matrix when scanning a band downward. The quantization error of the pixel of interest indicated by “*” is diffused to the next pixel of interest (lower pixel) at a ratio of 7/16, and three adjacent pixels on the next row at ratios of 3/16, 5/16, and 1/16 from the top. FIG. 2B shows an error diffusion matrix when scanning a band upward. The quantization error of the pixel of interest is diffused to the next pixel of interest (upper pixel) at a ratio of 7/16, and three adjacent pixels on the next row at ratios of 1/16, 5/16, and 3/16 from the top.
An example in which an overlapping region is set and error diffusion processing is performed for a band image will be explained with reference to FIGS. 3A and 3B. As shown in FIG. 3A, for example, a two-pixel wide overlapping region 401 is set in a band 102 in error diffusion processing for a band 101. A pixel at the upper left corner (leftmost end of line L0) of the band 101 is set as the pixel of interest. Pixels are scanned down to perform error diffusion processing until a pixel at the left end of line L5 serves as the pixel of interest. Then, a pixel on the second row of line L5 is set as the pixel of interest. Pixels are scanned up to perform error diffusion processing until a pixel on the second row of line L0 serves as the pixel of interest. Scanning is alternately repeated till the final row, and error diffusion processing for the band 101 ends. After the end of error diffusion processing for the band 101, error diffusion processing is done for the band 102 and the two-pixel wide overlapping region 401 of a band 103 as a processing target region, as shown in FIG. 3B. The same processing is repeated till a band at the bottom.
This error diffusion processing diffuses the quantization error of the pixel of interest to pixels e, f, g, and h shown in FIG. 2C at ratios of 7/16, 3/16, 5/16, and ⅙ in processing an odd-numbered row. Also, the error diffusion processing diffuses the quantization error of the pixel of interest to pixels d, f, g, and h at ratios of 7/16, 1/16, 5/16, and 3/6 in processing an even-numbered row.
In error diffusion processing for the band 101, errors (to be referred to as a diffusion error A) are diffused from pixels 406 and 405 on boundary line L4 of the band 102 to a pixel 404 of interest on an even-numbered row on boundary line L3 of the band 101 shown in FIG. 3B. In error diffusion processing for the band 102, errors (to be referred to as a diffusion error B) are diffused from the pixels 406 and 405 to the pixel 404 of interest (though these errors are not diffused actually). No dot pattern mismatch occurs if the values of the diffusion errors A and B are approximate to each other.
In error diffusion processing for the band 101, the diffusion error A actually diffused from the pixels 406 and 405 to the pixel 404 of interest is affected by the quantization error of line L5 of the overlapping region 401 because of bidirectional pixel scanning. In error diffusion processing for the band 102, the diffusion error B which is not actually diffused from the pixels 406 and 405 to the pixel 404 of interest is affected by the quantization error of line L5 and further by the quantization error of a lower line. In general, therefore, the values of the diffusion errors A and B are not approximate to each other. The invention in patent literature 2 is free from this problem because error diffusion processing is performed by scanning pixels only downward.
When error diffusion processing is executed by scanning a band in two directions perpendicular to its longitudinal direction, even the arranged overlapping region cannot prevent thread-like image quality degradation at the boundary. Arranging an overlapping region requires a larger capacity of memory storage, and increases the calculation amount and installation cost.